package com.algorithm.datastructure;


import java.util.Iterator;
import java.util.function.Consumer;

/**
 * 单向链表(带哨兵)
 */
public class SinglyLinkedListSentinel implements Iterable<Integer> {
    private Node head = new Node(555, null); //头指针

    @Override
    public Iterator<Integer> iterator() {
        //匿名内部类
        return new NodeIterator();
    }

    private class NodeIterator implements Iterator<Integer> {
        Node p = head.next;

        @Override
        public boolean hasNext() {
            return p != null;
        }

        @Override
        public Integer next() {
            int v = p.value;
            p = p.next;
            return v;
        }
    }

    /**
     * 节点类
     */
    private static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void loop1(Consumer consumer) {
        Node p = head.next;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    public void loop2(Consumer consumer) {
        for (Node p = head.next; p != null; p = p.next) {
            consumer.accept(p.value);
        }

    }

    private Node findLast() {
        Node p;
        for (p = head; p.next != null; p = p.next) {
        }
        return p;
    }

    public void addLast(int value) {
        Node last = findLast();
        last.next = new Node(value, null);
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;

    }

    public int get(int index) {
        Node node = findNode(index);
        if (node == null) {
            return illegalIndex(index);
        }
        return node.value;
    }

    private int illegalIndex(int index) {
        throw new IllegalArgumentException(
                String.format("index [%d]不合法%n", index));
    }


    public void insert(int index, int value) {
        Node before = findNode(index - 1);
        if (before == null) {
            illegalIndex(index);
        }
        before.next = new Node(value, before.next);
    }

    public void removeFirst() {
        remove(0);
    }

    public void remove(int index) {
        Node node = findNode(index - 1);
        if (node == null) {
            illegalIndex(index);
        }
        Node removed = node.next;
        if (removed == null) {
            illegalIndex(index);
        }
        node.next = removed.next;//没有引用，垃圾回收机制释放内存

    }

    public static void main(String[] args) {
        SinglyLinkedListSentinel singlyLinkedList = new SinglyLinkedListSentinel();
        singlyLinkedList.addFirst(1);
        singlyLinkedList.addFirst(2);
        singlyLinkedList.addFirst(3);
        singlyLinkedList.addFirst(4);

        singlyLinkedList.loop1(val -> {
            System.out.println((int) val + 1);
        });
        System.out.println("------------------");
        singlyLinkedList.loop2(val -> {
            System.out.println(val);
        });
        System.out.println("-----迭代器遍历--------");
        for (Integer val : singlyLinkedList) {
            System.out.println(val);
        }

        System.out.println("---singlyLinkedList2-------");
        SinglyLinkedListSentinel singlyLinkedList2 = new SinglyLinkedListSentinel();
        singlyLinkedList2.addLast(1);
        singlyLinkedList2.addLast(5);
        singlyLinkedList2.addLast(2);
        singlyLinkedList2.addLast(4);
        singlyLinkedList2.forEach(val -> {
            System.out.println(val);
        });
        System.out.println("------get(index)---------");
        System.out.println(singlyLinkedList2.get(1));
        System.out.println(singlyLinkedList2.get(2));
        System.out.println("----insert-----");
        singlyLinkedList2.insert(1, 8);
        singlyLinkedList2.insert(5, 5);
        singlyLinkedList2.forEach(val -> {
            System.out.println(val);
        });
        System.out.println("----removeFirst-----");
        singlyLinkedList2.removeFirst();
        singlyLinkedList2.removeFirst();
        singlyLinkedList2.forEach(val -> {
            System.out.println(val);
        });
        System.out.println("----remove-----");
        singlyLinkedList2.remove(1);
        singlyLinkedList2.remove(1);
        singlyLinkedList2.addFirst(55);
        singlyLinkedList2.forEach(val -> {
            System.out.println(val);
        });
        System.out.println(singlyLinkedList2.get(-1));
    }
}


